/*
提交链接:https://leetcode.cn/problems/count-of-integers/description/
2719. 统计整数数目
赖德檀 2024/10/5
*/

class Solution {
public:
int len,mx,mi;
vector<char>arr;
int MOD = 1000000007;
int dp[23][401][2];  //挂表，记忆化搜索

void test()
{
    for(int i=0;i<len;i++)  //位数
    {
        for(int j=0;j<=mx;j++) //每一位数的总和最大值
        {
            dp[i][j][0]=-1;
            dp[i][j][1]=-1;
        }
    }
}

    bool check()
    {
        int sum=0;
        for(char c:arr)
        sum+=c-'0';
        return (sum>=mi&&sum<=mx);
    }

//从num的高位即i位出发
//之前决定的数字累加和为num
//之前决定的已经比num小，后续可以自由选择，fe=1
//之前决定的和num一样，后续还可以自由选择，fe=0
    int f(int i,int sum,int fe)
    {
        if(sum>mx) return 0;
        if(sum+(len-i)*9<mi) return 0; 
        //sum + 剩下的位数*9即*最大值都小于mi，说明达不到要求

        if(i==len) return 1;

        if(dp[i][sum][fe]!=-1)  //以前找过这个数了
        return dp[i][sum][fe];

        int cnt=arr[i]-'0';
        int ans=0;
        if(fe==0)//不能自由选择
        {
            for(int j=0;j<cnt;j++)//可以出现重复数字
            {
                ans = (ans+f(i+1,sum+j,1))%MOD;
            }
            ans= (ans+f(i+1,sum+cnt,0))%MOD;
        }
        else//自由选择
        {
            for(int j=0;j<=9;j++)
            ans =(ans+f(i+1,sum+j,1))%MOD;
        }
            dp[i][sum][fe]=ans;
        return ans;
    }

    int count(string num1, string num2, int min_sum, int max_sum) {
        //求[num1,num2] ==> [0,num2]-[0,num1]
        int ans=0;
        for(auto c:num2)
        arr.push_back(c);
        len=num2.size();
        mx=max_sum;
        mi=min_sum;
        test();  //初始化表
        ans+=f(0,0,0);
        arr.clear();
        for(auto c:num1)
        arr.push_back(c);
        len=num1.size();
        test();  //初始化表
        ans=(ans-f(0,0,0)+MOD)%MOD;
        if(check())  
        //判断最小值是不是，比如7-5=2.没有判断到5，只有6,7，所以对5判断下
        {
            ans=(ans+1)%MOD;
        }
        return ans;
    }
};